Finite element analysis (FEA) is one of the popular CAE analyses widely used in industry to model and solve engineering problems related to complex systems such as three-dimensional non-linear structural design and analysis. FEA derives its name from the manner in which the geometry of the object under consideration is specified. With the advent of the modern digital computer, FEA has been implemented as FEA software. Basically, the FEA software is provided with a model of the geometric description and the associated material properties at each point within the model. In this model, the geometry of the system under analysis is represented by solids, shells and beams of various sizes, which are called elements. The corners of the elements are referred to as nodes. Each node has 6-degrees of freedom in three-dimensional space. The model is comprised of a finite number of elements, which are assigned a material name to associate with material properties. The model thus represents the physical space occupied by the object under analysis along with its immediate surroundings. The FEA software then refers to a table in which the properties (e.g., stress-strain constitutive equation, Young's modulus, Poisson's ratio, thermo-conductivity) of each material type are tabulated. Additionally, the conditions at the boundary of the object (i.e., loadings, physical constraints, etc.) are specified. In this fashion a model of the object and its environment is created.
There are two types of FEA software—explicit and implicit. The present invention is related to implicit FEA software, which requires solving a system of simultaneous linear equations with one equation representing each degree-of-freedom. For example, a static analysis involves solving N simultaneous linear equations represented by an N×N stiffness matrix with N unknown displacements and N nodal forces and/or moments as the right hand side of the simultaneous linear equations. N is a positive integer. With the improvement of the finite element software and computer hardware technologies, many today's FEA model includes huge number of unknowns (e.g., often in the order of millions). The N×N matrix for a FEA model is sparse (i.e., there are many zeros). A number of techniques have been used to improve the performance of solving such a matrix both in serial and parallel computations. In a distributed memory multi-processor computer system, one of the keys to improve sparse matrix solver performance is to partition the matrix in a partition scheme that can reduce the inter-processor communications. However, partitioning a large sparse matrix is not an easy task. Prior art approaches are generally based on “Nested Dissection of a Regular Finite Element Mesh” by Alan George, SIAM Journal on Numerical Analysis, Vol. 10, No. 2. April 1973.
However the prior art approaches do not work well in a distributed memory computer system. Therefore, it would be desirable to have improved methods and systems for partitioning a graph representing a matrix to be used in CAE analysis of a physical domain in a distributed memory multi-processor computer system.